package leet;

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

/**
 * In a forest, each rabbit has some color. Some subset of rabbits (possibly all
 * of them) tell you how many other rabbits have the same color as them. Those
 * answers are placed in an array.
 * 
 * Return the minimum number of rabbits that could be in the forest.
 * 
 * @author zhujunbing
 * @date 2019年4月16日
 */
public class Leet0781 {

	/*
	 * Examples: Input: answers = [1, 1, 2] Output: 5 Explanation: The two rabbits
	 * that answered "1" could both be the same color, say red. The rabbit than
	 * answered "2" can't be red or the answers would be inconsistent. Say the
	 * rabbit that answered "2" was blue. Then there should be 2 other blue rabbits
	 * in the forest that didn't answer into the array. The smallest possible number
	 * of rabbits in the forest is therefore 5: 3 that answered plus 2 that didn't.
	 * 
	 * Input: answers = [10, 10, 10] Output: 11
	 * 
	 * Input: answers = [] Output: 0
	 */

	/*
	 * 题目意思： answers是所有兔子的一个子集， [1,1,2]表示 第一只兔子说有一只兔子颜色和他一样，第二只说有一只和他一样，第三只说有两只和他一样
	 * 所以最小值是（一种比较容易计算的情况），第一只和第二只颜色一样，还有两只和第三只一样 总共5只
	 */

	public static void main(String[] args) {

		Leet0781 leet781 = new Leet0781();
		int[] answers = { 1, 1, 2 };
		int numRabbits = leet781.numRabbits(answers);

		System.out.println(numRabbits);
	}

	/**
	 * 把相同数的 统计下就好了。
	 * 
	 * @param answers
	 * @return
	 * @date 2019年4月16日
	 */
	public int numRabbits(int[] answers) {

		Map<Integer, Integer> map = new HashMap<>();

		for (int i : answers) {
			map.put(i + 1, map.getOrDefault(i + 1, 0) + 1);
		}

		int count = 0;

		for (Entry<Integer, Integer> entry : map.entrySet()) {

			Integer value = entry.getValue();
			Integer key = entry.getKey();
			int a = value % key;
			count += a == 0 ? value : value + key - a;
		}

		return count;
	}
}
